package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _120寻找两个正序数组的中位数
 * @description
 * @date 2023/08/16 20:36
 * <p>
 * ******************************************************
 */
public class _120寻找两个正序数组的中位数 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        int mid = (n2 + n1) / 2;
        boolean flag = (n1 % 2 + n2 % 2) % 2 == 1;
        int p = 0;
        int q = 0;
        int midValue = Integer.MIN_VALUE;
        int next = Integer.MIN_VALUE;

        while (mid >= 0) {
            mid--;
            if (next != Integer.MIN_VALUE) {
                midValue = next;
            }
            if (p >= n1) {
                next = nums2[q++];
            } else if (q >= n2) {
                next = nums1[p++];
            } else {
                if (nums1[p] > nums2[q]) {
                    next = nums2[q++];
                } else {
                    next = nums1[p++];
                }
            }
        }
        return flag ? next : (((double)midValue + (double)next) / 2);
    }

    public static void main(String[] args) {
        _120寻找两个正序数组的中位数 s = new _120寻找两个正序数组的中位数();
        System.out.println(s.findMedianSortedArrays(new int[]{}, new int[]{1}));
    }
}
